import java.util.*;

class TextBinaryTree{
    static class TreeNode{
        public char val;
        public TreeNode lift;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree(){
        TreeNode treeNode=new TreeNode('A');
        TreeNode treeNode1=new TreeNode('B');
        TreeNode treeNode2=new TreeNode('C');
        TreeNode treeNode3=new TreeNode('D');
        TreeNode treeNode4=new TreeNode('E');
        TreeNode treeNode5=new TreeNode('F');
        TreeNode treeNode6=new TreeNode('G');
        TreeNode treeNode7=new TreeNode('H');
        treeNode.lift=treeNode1;
        treeNode.right=treeNode2;
        treeNode1.lift=treeNode3;
        treeNode1.right=treeNode4;
        treeNode2.lift=treeNode5;
        treeNode2.right=treeNode6;
        treeNode4.right=treeNode7;
        return treeNode;
    }
    //根据前序遍历，和中序遍历确定二叉树
    public int proIndex;
    public int findRootIndex(char[] midOrder,int inBegin,int inEnd,char k){
        for (int i = inBegin; i <=inEnd ; i++) {
            if (midOrder[i]==k){
                return 1;
            }
        }return -1;
    }

    private TreeNode buildTreeChildPM(char[] proOrder,char[] midOrder, int inBegin,int inEnd){
        if(inBegin>inEnd){
            return null;
        }
        TreeNode root=new TreeNode(proOrder[proIndex]);
        proIndex++;
        int rootIndex=findRootIndex(proOrder,inBegin,inEnd,proOrder[proIndex]);
        root.lift=buildTreeChildPM( proOrder, midOrder, inBegin,rootIndex-1);
        root.right=buildTreeChildPM( proOrder, midOrder, rootIndex+1,inEnd);
        return root;


}
    public TreeNode buildTreePM(char[] proOrder,char[] midOrder){
        return buildTreeChildPM(proOrder,midOrder,0,midOrder.length-1);
    }

    //根据中序遍历和后序遍历，生成一个二叉树
    private TreeNode buildTreeChildMP(char[] midOrder,char[] postOrder, int inBegin,int inEnd){
        if(inBegin>inEnd){
            return null;
        }
        TreeNode root=new TreeNode(postOrder[proIndex]);

        int rootIndex=findRootIndex(postOrder,inBegin,inEnd,postOrder[proIndex]);
        proIndex++;
        root.right=buildTreeChildPM(midOrder, postOrder, rootIndex+1,inEnd);
        root.lift=buildTreeChildPM( midOrder, postOrder, inBegin,rootIndex-1);

        return root;


    }
    public TreeNode buildTreeMP(char[] midOrder,char[] postOrder){
        proIndex=postOrder.length-1;
        return buildTreeChildMP(midOrder,postOrder,0,midOrder.length-1);
    }
    //遍历
    public void preOrder(TreeNode root){
        if (root==null){
            return;
        }
        System.out.println(root.val+" ");
        preOrder(root.lift);
        preOrder(root.right);
    }

    //非递归遍历，栈实现
    public void preOrder1(TreeNode root){
        Stack<TreeNode> stack= new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.println(cur.val+" ");
                cur = cur.lift;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }
    public void midOrder(TreeNode root){
        if (root==null){
            return;
        }
        midOrder(root.lift);
        System.out.println(root.val+" ");
        midOrder(root.right);
    }
    public void midOrder1(TreeNode root){
        Stack<TreeNode> stack= new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.lift;
            }
            TreeNode top = stack.pop();
            System.out.println(top.val+" ");
            cur = top.right;
        }
    }
    public void postOrder(TreeNode root){
        if (root==null){
            return;
        }
        postOrder(root.lift);
        postOrder(root.right);
        System.out.println(root.val+" ");
    }
    public void postOrder1(TreeNode root){
        Stack<TreeNode> stack= new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while (cur!=null||!stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.lift;
            }
            TreeNode top = stack.peek();
            if (top.right==null||top.right==prev){
                stack.pop();
                System.out.println(top.val+" ");
                prev=top;
            }else {
                cur = top.right;
            }


        }
    }
    //层次遍历
    public void levelOrder(TreeNode root){
        if (root==null){
            return;
        }
        Queue<TreeNode> queue=new LinkedList();
        TreeNode cur=null;
        queue.offer(root);
        while (!queue.isEmpty()){
            cur=queue.peek();
            System.out.print(queue.poll().val+" ");
            if (cur.lift!=null){
                queue.offer(cur.lift);
            }
            if (cur.right!=null) {
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }
    public List<List<Character>>levelOrder1(TreeNode root){
        List<List<Character>> ret=new ArrayList<>();
        if (root==null){
            return ret;
        }
        Queue<TreeNode> queue=new LinkedList();
        TreeNode cur=null;
        queue.offer(root);
        while (!queue.isEmpty()){
            int size=queue.size();
            List<Character> list=new ArrayList<>();
            while (size>0){
                cur=queue.poll();
                list.add(cur.val);
                if (cur.lift!=null){
                    queue.offer(cur.lift);
                }
                if (cur.right!=null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
    //节点个数
    public int  size(TreeNode root){
        if (root==null){
            return 0;
        }
        int ret=size(root.lift)+size(root.right)+1;
        return ret;
    }

    public static int sizeNode;
    public void size2(TreeNode root){
        if (root==null){
            return ;
        }
        sizeNode++;
        size2(root.lift);
        size2(root.right);
    }
//叶子的节点个数
    public int  getLeafNodeCount(TreeNode root){
        if (root==null){
            return 0;
        }
        if (root.lift==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.lift)+
                getLeafNodeCount(root.right);

    }
    public static int leafSize;
    public void getLeafNodeCount2(TreeNode root){
        if (root==null){
            return ;
        }
        if (root.lift==null&&root.right==null){
            leafSize++;
        }
        getLeafNodeCount2(root.lift);
        getLeafNodeCount2(root.right);
    }
    //第k层有多少个节点
    public int getKLevelNodeCount(TreeNode root,int k){
        if (root==null){
            return 0;
        }
        if (k==1){
            return 1;
        }
        return getKLevelNodeCount(root.lift,k-1)
                +getKLevelNodeCount(root.right,k-1);
    }
    public int getHeight(TreeNode root){
        if (root==null){
            return 0;
        }
       int leftHeight=getHeight(root.lift);
       int rightHeight=getHeight(root.right);
       return Math.max(leftHeight,rightHeight)+1;
    }
    //遍历二叉树找到val所在的节点
    public TreeNode find(TreeNode root,char val){
        if (root==null){
            return null;
        }
        if (root.val==val){
            return root;
        }
         TreeNode ret=find(root.right,val);
        if (ret!=null){
            return ret;
        }
        ret=find(root.lift,val);
        if (ret!=null){
            return ret;
        }
         return null;
    }
    public TreeNode invertTree(TreeNode root){
        if (root==null){
            return null;
        }
        if (root.right==null&&root.lift==null){
            return root;
        }
        TreeNode tmp;
        tmp=root.lift;
        root.lift=root.right;
        root.right=tmp;
        invertTree(root.right);
        invertTree(root.lift);
        return root;
    }

    //平衡二叉树，所有子树的高度差不超过一
    //该方法的时间复杂度为o（n^2）
    public boolean isBalanced(TreeNode root){
        if (root==null){
            return true;
        }
        int liftH=getHeight(root.lift);
        int rightH=getHeight(root.right);

        return Math.abs(liftH-rightH)<1
                &&isBalanced(root.lift)
                &&isBalanced(root.right);
    }
//该方法时间复杂度为o（n）
    public boolean isBalanced1(TreeNode root){
        if (root==null){
            return true;
        }
       return maxHeight(root)>=1;
    }
    public int maxHeight(TreeNode root){
        if (root==null){
            return 0;
        }
        int leftHeight=maxHeight(root.lift);
        if (leftHeight<0){
            return -1;
        }
        int rightHeight=getHeight(root.right);
        if (rightHeight<0){
            return -1;
        }
        if (Math.abs(leftHeight-rightHeight)<=1){
            return Math.max(leftHeight,rightHeight)+1;
        }else {
            return -1;
        }
    }
    public int maxHeight1(TreeNode root){
        if (root==null){
            return 0;
        }
        int leftHeight=maxHeight(root.lift);
        if (leftHeight<0){
            return -1;
        }
        int rightHeight=getHeight(root.right);
        if (rightHeight>=0&&rightHeight>=0&&
                Math.abs(leftHeight-rightHeight)<=1){
            return Math.max(leftHeight,rightHeight)+1;
        }else {
            return -1;
        }
    }
    //对称二叉树
    public boolean isSymmetric(TreeNode root){
        if (root==null){
            return true;
        }
        return isSymmetricChild(root.lift,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,
                                    TreeNode rightTree){
        if (leftTree!=null&&rightTree==null
                ||leftTree==null&&rightTree!=null){
            return false;
        }
        if (leftTree==null&&rightTree==null){
            return true;
        }
        if (leftTree.val!=rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.lift,rightTree.right)
                &&isSymmetricChild(leftTree.right,rightTree.lift);
    }
//判断是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if (root==null){
            return true;
        }
        Queue<TreeNode> queue=new LinkedList();
        TreeNode cur=null;
        queue.offer(root);
        while (!queue.isEmpty()){
                cur= queue.poll();
                if (cur==null){
                    break;
                }
                queue.offer(cur.lift);
                queue.offer(cur.right);
        }
      while (!queue.isEmpty()){
          TreeNode node=queue.peek();
          if (node!=null){
              return false;
          }else {
              queue.poll();
          }
      }
      return true;
    }
    //找一棵树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        if (root==null){
            return null;
        }
        if (p==root||q==root){
            return root;
        }
        TreeNode leftTree=lowestCommonAncestor(root.lift,p,q);

        TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
        if (leftTree!=null&&rightTree!=null){
            return root;
        }else if (leftTree!=null){
            return leftTree;
        }else {
            return rightTree;
        }
    }
    public boolean getPath(TreeNode root ,TreeNode node,Stack<TreeNode> stack){
        if (root==null){
            return false;
        }
        stack.push(root);
        if (root==node){
            return true;
        }
        boolean flg=getPath(root.lift,node,stack);
        if (flg==true){
            return true;
        }
        boolean flg2=getPath(root.right,node,stack);
        if (flg2==true){
            return true;
        }
        stack.pop();
        return false;

    }
    public TreeNode lowestCommonAncestor1(TreeNode root,TreeNode p,TreeNode q) {
        if (root==null){
            return root;
        }
        Stack<TreeNode> stackP=new Stack<>();
        getPath(root,p,stackP);
        Stack<TreeNode> stackQ=new Stack<>();
        getPath(root,p,stackQ);
        int sizeP=stackP.size();
        int sizeQ=stackQ.size();
        if (sizeP>sizeQ){
            int size=sizeP-sizeQ;
            while (size!=0){
                stackP.pop();
                size--;
            }
        }else {
            int size=sizeQ-sizeP;
            while (size!=0) {
                stackQ.pop();
                size--;
            }
        }
        while (!stackP.empty()&&!stackQ.empty()){
            if (stackP.peek()==stackQ.peek()){
                return stackP.peek();
            }else {
                stackP.pop();
                stackQ.pop();
            }
        }
        return null;

    }
    //输入root=【1,2,3,4】根据前序遍历
    //输出“1（2（4））(3)”
    private void tree2strChild(TreeNode root,StringBuilder stringBuilder){
        if (root==null){
            return;
        }
        stringBuilder.append(root.val);
        if (root.lift!=null){
            stringBuilder.append("(");
            tree2strChild(root.lift,stringBuilder);
            stringBuilder.append(")");
        }else {
            if (root.right!=null){
                stringBuilder.append("()");
            }else {
                return;
            }
        }
        if (root.right==null){
            return;
        }else {
            stringBuilder.append("(");
            tree2strChild(root.right,stringBuilder);
            stringBuilder.append(")");
        }
    }
    public String tree2str(TreeNode root){
        StringBuilder stringBuilder=new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();

    }

    }


public class Text2 {
    //一棵树是否为另一棵数的子树
    public boolean isSubTree(TextBinaryTree.TreeNode root,
                             TextBinaryTree.TreeNode subRoot){
        if(root==null){
            return false;
        }
        if (isSameTree(root,subRoot)){
            return true;
        }
        if (isSubTree((root.lift),subRoot)){
            return true;
        }
        if (isSubTree((root.right),subRoot)){
            return true;
        }
        return false;
    }
    //是否为两颗相同的树
    public boolean isSameTree(TextBinaryTree.TreeNode root1, TextBinaryTree.TreeNode root2){
        if (root1!=null&&root2==null
                ||root1==null&&root2!=null){
            return false;
        }
        if (root1==null&&root2==null){
            return true;
        }
        if (root1.val!=root2.val){
            return false;
        }
        return isSameTree(root1.lift,root2.lift)
                &&isSameTree(root1.right,root2.right);
    }


    public static void main(String[] args) {
        TextBinaryTree textBinaryTree=new TextBinaryTree();
        TextBinaryTree.TreeNode root=textBinaryTree.createTree();
        System.out.println(textBinaryTree.tree2str(root));
        System.out.println(textBinaryTree.levelOrder1(root));
        System.out.println("========");

        System.out.println(textBinaryTree.isCompleteTree(root));


    }
}
